package 集合.hashCode与equals;
/*
“两个包装类型在使用“==”进行判断的时候，判断的是其指向的地址是否相等，由于是两个对象，所以地址是不同的。”

“而 chenmo.equals(wanger) 的输出结果为 true，是因为 equals() 方法内部比较的是两个 int 值是否相等。”
 
我们知道Map是一种键-值（key-value）映射表，可以通过key快速查找对应的value。

以HashMap为例，观察下面的代码：

Map<String, Person> map = new HashMap<>();
map.put("a", new Person("Xiao Ming"));
map.put("b", new Person("Xiao Hong"));
map.put("c", new Person("Xiao Jun"));

map.get("a"); // Person("Xiao Ming")
map.get("x"); // null
HashMap之所以能根据key直接拿到value，原因是它内部通过空间换时间的方法，用一个大数组存储所有value，并根据key直接计算出value应该存储在哪个索引：

  ┌───┐
0 │   │
  ├───┤
1 │ ●─┼───> Person("Xiao Ming")
  ├───┤
2 │   │
  ├───┤
3 │   │
  ├───┤
4 │   │
  ├───┤
5 │ ●─┼───> Person("Xiao Hong")
  ├───┤
6 │ ●─┼───> Person("Xiao Jun")
  ├───┤
7 │   │
  └───┘
如果key的值为"a"，计算得到的索引总是1，因此返回value为Person("Xiao Ming")，如果key的值为"b"，计算得到的索引总是5，因此返
回value为Person("Xiao Hong")，这样，就不必遍历整个数组，即可直接读取key对应的value。
当我们使用key存取value的时候，就会引出一个问题：
我们放入Map的key是字符串"a"，但是，当我们获取Map的value时，传入的变量不一定就是放入的那个key对象。
换句话讲，两个key应该是内容相同，但不一定是同一个对象。测试代码如下：

import java.util.HashMap;
import java.util.Map;
public class 编写equals和hashCode {
    public static void main(String[] args) {
        String key1 = "a";
        Map<String, Integer> map = new HashMap<>();
        map.put(key1, 123);

        String key2 = new String("a");
        map.get(key2); // 123

        System.out.println(key1 == key2); // false
        System.out.println(key1.equals(key2)); // true
    }
}

因为在Map的内部，对key做比较是通过equals()实现的，这一点和List查找元素需要正确覆写equals()是一样的，即正确使用Map必须保证：作为key的对象必须正确
覆写equals()方法。

我们经常使用String作为key，因为String已经正确覆写了equals()方法。但如果我们放入的key是一个自己写的类，就必须保证正确覆写了equals()方法。

我们再思考一下HashMap为什么能通过key直接计算出value存储的索引。相同的key对象（使用equals()判断时返回true）必须要计算出相同的索引，否则，相同的key每次取出的value就不一定对。

通过key计算索引的方式就是调用key对象的hashCode()方法，它返回一个int整数。HashMap正是通过这个方法直接定位key对应的value的索引，继而直接返回value。

因此，正确使用Map必须保证：

1.作为key的对象必须正确覆写equals()方法，相等的两个key实例调用equals()必须返回true；
2.作为key的对象还必须正确覆写hashCode()方法，且hashCode()方法要严格遵循以下规范：
	◾如果两个对象相等，则两个对象的hashCode()必须相等；
	◾如果两个对象不相等，则两个对象的hashCode()尽量不要相等。

即对应两个实例a和b：
	◾如果a和b相等，那么a.equals(b)一定为true，则a.hashCode()必须等于b.hashCode()；
	◾如果a和b不相等，那么a.equals(b)一定为false，则a.hashCode()和b.hashCode()尽量不要相等。

上述第一条规范是正确性，必须保证实现，否则HashMap不能正常工作。而第二条如果尽量满足，则可以保证查询效率，因为不同的对象，如果返回相
同的hashCode()，会造成Map内部存储冲突，使存取的效率下降。

从理论上来说，对于两个不同对象，它们通过 hashCode() 方法计算后的值可能相同。因此，不能使用 hashCode() 方法来判断两个对象是否相等，必须得通过 equals() 方法。

也就是说：
·如果两个对象调用 equals() 方法得到的结果为 true，调用 hashCode() 方法得到的结果必定相等；
·如果两个对象调用 hashCode() 方法得到的结果不相等，调用 equals() 方法得到的结果必定为 false；

反之：
·如果两个对象调用 equals() 方法得到的结果为 false，调用 hashCode() 方法得到的结果不一定不相等；
·如果两个对象调用 hashCode() 方法得到的结果相等，调用 equals() 方法得到的结果不一定为 true；

正确编写equals()的方法我们已经在编写equals方法一节中讲过了，以Person类为例：

public class Person {
    String firstName;
    String lastName;
    int age;
}
把需要比较的字段找出来：
	◾firstName 
	◾lastName 
	◾age
然后，引用类型使用Objects.equals()比较，基本类型使用==比较。

在正确实现equals()的基础上，我们还需要正确实现hashCode()，即上述3个字段分别相同的实例，hashCode()返回的int必须相同：
*/
/*
class Persone {
	String firstName;
	String lastName;
	int age;

	public Persone(String firstName, String lastName, int age) {
		this.firstName = firstName;
		this.lastName = lastName;
		this.age = age;
	}

	@Override
	public int hashCode() { // int 集合.Person.hashCode()
		int h = 0;
		h = 31 * h + firstName.hashCode();// int java.lang.String.hashCode()
		h = 31 * h + lastName.hashCode();// int java.lang.String.hashCode()
		h = 31 * h + age;
		return h;
	}
}

public class 编写equals和hashCode {
	public static void main(String[] args) {
		Persone p1 = new Persone("a1", "b1", 10);
		Persone p2 = new Persone("a2", "b2", 20);
		System.out.println(p1.hashCode());
		System.out.println(p2.hashCode());
	}
}
*/
/*
注意到String类已经正确实现了hashCode()方法，我们在计算Person的hashCode()时，反复使用31*h，这样做的目的是为了尽量把不同
的Person实例的hashCode()均匀分布到整个int范围。

和实现equals()方法遇到的问题类似，如果firstName或lastName为null，上述代码工作起来就会抛NullPointerException。为了解
决这个问题，我们在计算hashCode()的时候，经常借助Objects.hash()来计算：

int hashCode() {
    return Objects.hash(firstName, lastName, age);
}

所以，编写equals()和hashCode()遵循的原则是：
equals()用到的用于比较的每一个字段，都必须在hashCode()中用于计算；
equals()中没有使用到的字段，绝不可放在hashCode()中计算。
另外注意，对于放入HashMap的value对象，没有任何要求。

《延伸阅读》
既然HashMap内部使用了数组，通过计算key的hashCode()直接定位value所在的索引，那么第一个问题来了：hashCode()返回的int范围高达±21亿，先不
考虑负数，HashMap内部使用的数组得有多大？

实际上HashMap初始化时默认的数组大小只有16，任何key，无论它的hashCode()有多大，都可以简单地通过：
int index = key.hashCode() & 0xf; // 0xf = 15

把索引确定在0～15，即永远不会超出数组范围，上述算法只是一种最简单的实现。

第二个问题：如果添加超过16个key-value到HashMap，数组不够用了怎么办？

添加超过一定数量的key-value时，HashMap会在内部自动扩容，每次扩容一倍，即长度为16的数组扩展为长度32，相应地，需要重新确定hashCode()计算的索引位置。
例如，对长度为32的数组计算hashCode()对应的索引，计算方式要改为：
int index = key.hashCode() & 0x1f; // 0x1f = 31
由于扩容会导致重新分布已有的key-value，所以，频繁扩容对HashMap的性能影响很大。如果我们确定要使用一个容量为10000个key-value的HashMap，更好的方
式是创建HashMap时就指定容量：

Map<String, Integer> map = new HashMap<>(10000);
虽然指定容量是10000，但HashMap内部的数组长度总是2的n次方(2^13=8192)，因此，实际数组长度被初始化为比10000大的16384(2的14次方,2^14=16384)。

最后一个问题：如果不同的两个key，例如"a"和"b"，它们的hashCode()恰好是相同的（这种情况是完全可能的，因为不相等的两个实例，只要求hashCode()尽量不
相等），那么，当我们放入：
map.put("a", new Person("Xiao Ming"));
map.put("b", new Person("Xiao Hong"));
时，由于计算出的数组索引相同，后面放入的"Xiao Hong"会不会把"Xiao Ming"覆盖了？

当然不会！使用Map的时候，只要key不相同，它们映射的value就互不干扰。但是，在HashMap内部，确实可能存在不同的key，映射到相同的hashCode()，即相同的
数组索引上，肿么办？

我们就假设"a"和"b"这两个key最终计算出的索引都是5，那么，在HashMap的数组中，实际存储的不是一个Person实例，而是一个List，它包含两个Entry，一个
是"a"的映射，一个是"b"的映射：

  ┌───┐
0 │   │
  ├───┤
1 │   │
  ├───┤
2 │   │
  ├───┤
3 │   │
  ├───┤
4 │   │
  ├───┤
5 │ ●─┼───> List<Entry<String, Person>>
  ├───┤
6 │   │
  ├───┤
7 │   │
  └───┘
在查找的时候，例如：

Person p = map.get("a");
HashMap内部通过"a"找到的实际上是List<Entry<String, Person>>，它还需要遍历这个List，并找到一个Entry，它的key字段是"a"，才能返回对应的Person实例。

我们把不同的key具有相同的hashCode()的情况称之为哈希冲突。在冲突的时候，一种最简单的解决办法是用List存储hashCode()相同的key-value。显然，如果冲突的概
率越大，这个List就越长，Map的get()方法效率就越低，这就是为什么要尽量满足条件二：

如果两个对象不相等，则两个对象的hashCode()尽量不要相等。
hashCode()方法编写得越好，HashMap工作的效率就越高。

小结
要正确使用HashMap，作为key的类必须正确覆写equals()和hashCode()方法；

一个类如果覆写了equals()，就必须覆写hashCode()，并且覆写规则是：

--如果equals()返回true，则hashCode()返回值必须相等；
--如果equals()返回false，则hashCode()返回值尽量不要相等。

实现hashCode()方法可以通过Objects.hashCode()辅助方法实现。


下面着重介绍一下常用类的hashCode()实现方法。

String类的hasCode()
public int hashCode() {
	int h=hash;
	if (h==0) {
		int off=offset;
		char value[]=value;
		int len=count;
		for (int i=0;i<len;i++) {
			h=31*h+val[value++];
		}
		hash=h;
	}
	return hash;
}

这段代码最有意思的还是hash的实现方法了。最终计算的hash值为：

s[0]31^(n-1)+s[1]31^(n-2)+...+s[n-1]
下面我们一步步地介绍这个hashCode方法。首先看方法的注释：
返回此字符串的哈希码。 字符串对象的哈希码计算为 s [0] * 31 ^（n-1）+ s [1] * 31 ^（n-2）+ ... + s [n-1] 使用int算术，其中s [i]是字符
串的第i个字符，n是字符串的长度，^表示幂。 （空字符串的哈希值为零。） 返回值： 此对象的哈希码值。

s[i]是string的第i个字符，n是String的长度。那为什么这里用31，而不是其它数呢?

31是个奇素数，如果乘数是偶数，并且乘法溢出的话，信息就会丢失，因为与2相乘等价于移位运算。使用素数的好处并不是很明显，但是习惯上都使用素数来计算散列结果。
31有个很好的特性，就是用移位和减法来代替乘法，可以得到更好的性能：31*i==(i<<5)-i。现在的VM可以自动完成这种优化。(From Effective Java)


2. hashcode 原理


2.1 Java equals()和 hashCode()的关系

hashcode 的理解

1.hashCode 的存在主要是用于查找的快捷性，如 Hashtable，HashMap 等，hashCode 是用来在散列存储结构中确定对象的存储地址的；

2.如果两个对象相同，就是适用于 equals(java.lang.Object) 方法，那么这两个对象的 hashCode 一定要相同；

3.如果对象的 equals 方法被重写，那么对象的 hashCode 也尽量重写，并且产生 hashCode 使用的对象，一定要和 equals 方法中使用的一致，否则就会违反
上面提到的第 2 点；

4.两个对象的 hashCode 相同，并不一定表示两个对象就相同，也就是不一定适用于 equals(java.lang.Object) 方法，只能够说明这两个对象在散列存储结构
中，如 Hashtable，他们 “存放在同一个篮子里” 。

再归纳一下就是 hashCode 是用于查找使用的，而 equals 是用于比较两个对象的是否相等的。以下这段话是从别人帖子回复拷贝过来的，说的很形象：

(1) hashcode 是用来查找的，如果你学过数据结构就应该知道，在查找和排序说过：假如内存中有这样的位置 [0 1 2 3 4 5 6 7] 而我有个类，这个类有个字段
叫 ID,我要把这个类存放在以上 8 个位置之一，如果不用 hashcode 而任意存放，那么当查找时就需要到这八个位置里挨个去找，或者用类似二分法的算法。 但如果
用 hashcode 那就会使效率提高很多。

我们这个类中有个字段叫 ID,那么我们就定义我们的 hashcode 为 ID％8，然后把我们的类存放在取得得余数那个位置。比如我们的 ID 为 9，9 除 8 的余数
为 1，那么我们就把该类存在 1 这个位置，如果 ID 是 13，求得 的余数是 5，那么我们就把该类放在 5 这个位置。这样，以后在查找该类时就可以通过 ID 和 8 求
余数直接找到 存放的位置了。

(2) 但是如果两个类有相同的 hashcode 该怎么办呢（假设上面的 ID 不是唯一的），假如 9%8=1，17%8=1，那么这是不是合法的呢？回答是：可以这样。

那么如何判断呢？在这个时候就需要定义 equals 了。也就是说，我们先通过 hashcode 来判断两个类是否存放在一个桶里面，但是这个桶里面可以有很多类，那么我们
就需要通过 equals 来在这个桶里找到我们要的类。

那么。重写了 equals()，为什么还要重写 hashCode()呢？
想想，你要在一个桶里找东西，你必须先要找到这个桶啊，你不通过重写 hashcode()来找到桶，光重写 equals()有什么用啊

当我们要在HashMap中添加对象时，先调用这个对象的 hashCode() 方法，得到对应的哈希值，然后将哈希值和对象一起放到 HashMap 中。当我们
要再添加一个新的对象时：
·获取对象的哈希值；
·和之前HashMap中已经存在的哈希值进行比较，如果不相等，直接存进去；
·如果有相等的，再调用 equals() 方法进行对象之间的比较，如果相等，不存了；
·如果不等，说明哈希冲突了，增加一个链表，存放新的对象；
·如果链表的长度大于 8，转为红黑树来处理。
就这么一套下来，调用 equals() 方法的频率就大大降低了。也就是说，只要哈希算法足够的高效，把发生哈希冲突的频率降到最低，哈希表的效率就特别的高。

2.2 Object 的 hashcode 分析
*/

import java.util.HashSet;
import java.util.Set;

import lombok.Data;
@Data
public class 编写equals和hashCode {
    private int id;

//    @Override
//    public boolean equals(Object o) {
//        if (this == o) {
//      	  return true;
//      	  }
//        if (o == null || getClass() != o.getClass()) {
//      	  return false;
//      	  }
//        编写equals和hashCode that = (编写equals和hashCode) o;//强制转型
//        System.out.println("调用equals");
//        return id == that.id;
//        //return this.id == that.id;
//    }

    @Override
    public int hashCode() {
        return id % 10;//有意让hashCode相同，
    }
    public static void main(String[] args) {
    	编写equals和hashCode a = new 编写equals和hashCode();
    	编写equals和hashCode b = new 编写equals和hashCode();
        a.setId(1);
        b.setId(1);
        Set<编写equals和hashCode> set = new HashSet<>();
        set.add(a);
        set.add(b);//往set中追加对象时，会调用equals方法判断追加的对象是否与set中的对象相等。优先调用经覆写的equals,否则调用Object 默认的 equals()方法
        System.out.println(a.hashCode() == b.hashCode());
        System.out.println(a.equals(b));
        System.out.println(set);

        //运行结果：
        //true
        //false
        //[编写equals和hashCode(id=1), 编写equals和hashCode(id=1)]
    }
}

/*
//以上这个示例，我们只重写了 hashcode() 方法，从上面的结果可以看出，虽然两个对象的 hashcode 相等，但实际上两个对象并不相等。
//
//我们没有重写 equals()方法，那么就会调用 Object 默认的 equals()方法，是比较两个对象的引用是不是相同，实际上两个对象的引用肯定是不等的，这里我们将生
//成的对象放到了 HashSet 中，而 HashSet 中只能够存放唯一的对象，也就是相同的（适用于 equals 方法）的对象只会存放一个，但是这里实际上是两个对
//象 a,b 都被放到了 HashSet 中，这样 HashSet 就失去了他本身的意义了。 此时我们把 equals 方法给加上：
//@Override
//public boolean equals(Object o) {
//    if (this == o) return true;
//    if (o == null || getClass() != o.getClass()) return false;
//    DemoHashCode that = (DemoHashCode) o;
//    return id == that.id;
//}
//从结果我们可以看出，现在两个对象就完全相等了，HashSet 中也只存放了一份对象。

2.3 hashmap 的 hashcode 分析
hashMap 组成结构：hashMap 是由数组和链表组成；

◾hashMap 的存储：一个对象存储到 hashMap 中的位置是由其 key 的 hashcode 值决定的;
◾查hashMap查找key:  找 key 的时候 hashMap 会先根据 key 值的 hashcode 经过取余算法定位其所在数组的位置，再根据 key 的 equals 方法匹配
  相同 key 值获取对应相应的对象；

(1)HashMap 存储 key
◾存值规则： 把 Key 的 hashCode 与 HashMap 的容量 取余得出该 Key 存储在数组所在位置的下标 （源码定位 Key 存储在数组的哪个位置是
以 hashCode & (HashMap 容量-1)算法得出）

为了演示方便定义一个容量大小为 3 的 hashMap（其默认为 16）

HashMap map=newHashMap(3);
 
map.put("a",1); 得到key 为“a” 的hashcode 值为97然后根据 该值和hashMap 容量取余97%3得到存储位到数组下标为1;
 
map.put("b",2); 得到key 为“b” 的hashcode 值为98,98%3到存储位到数组下标为2;
 
map.put("c",3); 得到key 为“c” 的hashcode 值为99，99%3到存储位到数组下标为0;
 
map.put("d",4); 得到key 为“d” 的hashcode 值为100，100%3到存储位到数组下标为1;
 
map.put("e",5); 得到key 为“e” 的hashcode 值为101，101%3到存储位到数组下标为2;
 
map.put("f",6); 得到key 为“f” 的hashcode 值为102，102%3到存储位到数组下标为0;

数组    链表
┌───┐
│   │   ┌───┐  ┌───┐
│ 0 ├───┤ c ├──┤ f │
│   │   └───┘  └───┘
├───┤            
│   │   ┌───┐  ┌───┐
│ 1 ├───┤ a ├──┤ d │
│   │   └───┘  └───┘
├───┤            
│   │   ┌───┐  ┌───┐
│ 2 ├───┤ b ├──┤ e │
│   │   └───┘  └───┘
└───┘

(2) hashmap 查找 key

得到 key 在数组中的位置：根据上图，当我们获取 key 为“a”的对象时，那么我们首先获得 key 的 hashcode97%3 得到存储位到数组下标为 1;

匹配得到对应 key 值对象：得到数组下表为 1 的数据“a”和“c”对象， 然后再根据key.equals()来匹配获取对应 key 的数据对象；

hashcode 对于 HashMap:如果没有 hashcode 就意味着 HashMap 存储的时候是没有规律可寻的，那么每当我们 map.get()方法的时候，就要把 map 里面的对象一一拿出来
进行 equals 匹配，这样效率是不是会超级慢

3. hash 冲突
哈希表的内在行为也带来了相应的问题：即使使用有效的哈希算法，两个或多个对象可能具有相同的哈希码，即使两个对象不相等。因此，即使它们具有不同的散列值，它们的散列码也会指
向同一个桶。 这种情况通常被称为散列冲突。

解决 hash 冲突的方法，详细分析可以点此处查看：

◾链表法
◾开放寻址法

Java 中的 hashMap 是使用链表法解决 hash 冲突的

当两个或多个对象指向同一个存储桶时，它们只是存储在一个链表中。在这种情况下，哈希表是一个链表数组，每个具有相同哈希值的对象都附加到链表中的桶索引处。

在最坏的情况下，几个桶会绑定一个链表，而对链表中对象的检索将是线性执行的。
处理哈希冲突 简言之，为什么高效地实现 hashCode()如此重要？
Java8 也为 HashMap 的实现进行了增强，如果桶大小超过 8，节点入超过 64，则会转换为红黑树，而不是使用链表，这样当链表太长接近线性查找（复杂度为 O(n)）时
用红黑树 O(logN) 代替。
在最坏的情况下，几个桶会绑定一个链表，而对链表中对象的检索将是线性执行的。

处理哈希冲突 简言之，为什么高效地实现 hashCode()如此重要？

3.1 hashmap 和 hashcode 的联系

User 类中我们重写 hashcode 方法

@Data //使用这个注解可以省去实体类中大量的get()、 set()、 toString()等方法。
public class User {
    private long userId;
    private String userName;
    private String email;

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 31 * hash + (int) userId;
        hash = 31 * hash + (userName == null ? 0 : userName.hashCode());
        hash = 31 * hash + (email == null ? 0 : email.hashCode());
        System.out.println("hashCode() called - Computed hash: " + hash);
        return hash;
    }

    public User(Long userId, String userName, String email) {
        this.userId = userId;
        this.userName = userName;
        this.email = email;
    }
}

​应用程序的入口：

​​public class DemoHashMap {

    public static void main(String[] args) {
        Map<User, User> users = new HashMap<>();
        User user1 = new User(1L, "John", "john@domain.com");
        User user2 = new User(2L, "Jennifer", "jennifer@domain.com");
        User user3 = new User(3L, "Mary", "mary@domain.com");
        users.put(user1, user1);
        users.put(user2, user2);
        users.put(user3, user3);

        if (users.containsKey(user1)) {
            System.out.print("User found in the collection");
        }
    }
}

在这里，重要的是要注意，每次将对象存储在哈希映射中并使用 containsKey() 方法检查时，都会调用 hashCode() 并将计算出的哈希码打印到控制台
*/


